package version2024.medium;

import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ16 购物单   动态规划
 * @Date: created in 2024/12/28 星期六 11:26
 * @Modified By:
 */
public class HJ16_ShoppingList {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 注意 hasNext 和 hasNextLine 的区别
        while (sc.hasNextInt()) { // 注意 while 处理多个 case
            // 总预算
            int money = sc.nextInt();
            // 物品总数
            int n = sc.nextInt();

            if (n <= 0 || money <= 0) {
                System.out.println(0);
                continue;
            }

            // 构建物品类
            Good[] gs = new Good[n + 1];
            for (int i = 1; i <= n; i++) {
                // 主件
                int v = sc.nextInt();
                int w = sc.nextInt();
                int q = sc.nextInt();
                // 注意是从数组下标1开始加元素的
                gs[i] = new Good(v, w, q);
            }
            for (int i = 1; i <= n; i++) {
                // 附件
                int q = gs[i].q;

                if (q > 0) {
                    if (gs[q].a1 == 0) {
                        // 主件为q, 附件为当前的i
                        gs[q].setA1(i);
                    } else {
                        gs[q].setA2(i);
                    }
                }
            }

            int[][] dp = dp(money, gs);

            System.out.println(dp[n][money]);
        }
    }

    // 自下而上的算法
    public static int[][] dp(int money, Good[] gs) {
        // 输入：
        //  5 5
        //  2 3 5
        //  2 3 5
        //  1 3 0
        //  1 2 0
        //  1 1 0
        // dp
        //    0 1 2 3  4  5 商品编号
        // 0  0 0 0 0  0  0
        // 1  0 0 0 3  3  3
        // 2  0 0 0 5  5  5
        // 3  0 0 0 7  7  7
        // 4  0 0 0 10 10 10
        // 5  0 0 0 13 13 13
        // 预算
        int n = gs.length - 1;
        // dp数组是一个二维数组, x轴为商品编号, y轴为预算, 数组元素为最大满意度, 下标0都不使用
        int[][] dp = new int[n + 1][money + 1];

        for (int i = 1; i <= n; i++) {
            int v = 0, v1 = 0, v2 = 0, v3 = 0, tempdp = 0, tempdp1 = 0, tempdp2 = 0,
                    tempdp3 = 0;

            // 物品价格(主件)
            v = gs[i].v;
            // 满意度(主件)
            tempdp = gs[i].w * v;

            if (gs[i].a1 != 0) {
                // 物品价格(主件 + 附件1)
                v1 = gs[gs[i].a1].v + v;
                // 满意度(主件 + 附件1)
                // 这里别写成v1 * (w + w1) 是不对的
                tempdp1 = gs[gs[i].a1].v * gs[gs[i].a1].w + tempdp;
            }

            // 这个case不能少, 否则有用例通过不了
            if (gs[i].a2 != 0) {
                // 物品价格(主件 + 附件2)
                v2 = gs[gs[i].a2].v + v;
                // 满意度(主件 + 附件2)
                tempdp2 = gs[gs[i].a2].v * gs[gs[i].a2].w + tempdp;
            }

            if (gs[i].a1 != 0 && gs[i].a2 != 0) {
                // 物品价格(主件 + 附件1 + 附件2)
                v3 = gs[gs[i].a1].v + gs[gs[i].a2].v + v;
                // 满意度(主件 + 附件1 + 附件2)
                tempdp3 = gs[gs[i].a1].v * gs[gs[i].a1].w + gs[gs[i].a2].v * gs[gs[i].a2].w +
                        tempdp;
            }

            for (int j = 1; j <= money; j++) {
                if (gs[i].q > 0) {
                    // baseCase, 当物品i是附件时, 相当于跳过
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // baseCase, 当物品i非附件, 以物品i-1, 总金额相同的情况为初始化的值
                    dp[i][j] = dp[i - 1][j];
                    // 由于是求最高满意度, 用max
                    // 用初始化的值和上一个格子数组元素对应满意度+新满意度 比较
                    if (j >= v && v != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v] + tempdp);
                    }
                    if (j >= v1 && v1 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + tempdp1);
                    }
                    if (j >= v2 && v2 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + tempdp2);
                    }
                    if (j >= v3 && v3 != 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + tempdp3);
                    }
                }
            }
        }

        return dp;
    }

    /**
     * 定义物品类
     */
    private static class Good {
        // 物品的价格
        public int v;
        // 物品的重要度
        public int w;
        // 物品的主键编号
        public int q;
        // 附件1ID
        public int a1 = 0;
        // 附件2ID
        public int a2 = 0;

        public Good(int v, int w, int q) {
            this.v = v;
            this.w = w;
            this.q = q;
        }

        public void setA1(int a1) {
            this.a1 = a1;
        }

        public void setA2(int a2) {
            this.a2 = a2;
        }
    }
}
